/**
 * Comments were taken as-is from the questions sheet. Sorry...
 */

public abstract class MyArrayList {
	
	protected Object ar[]; 	//tableau interne
	protected int ps, ls; 		//tailles physique/logique
	protected int fact; 		//facteur
	protected int ct_added; 	//nombre d'ajouts
	protected int ct_accCp; 	//nombre cumulé de copies
	protected int ct_accTot; 	//nombre cumulé de tailles physiques
	protected int ct_accLog; 	//nombre cumulé de tailles logiques
	
	/**
	 * Initialise le tableau interne et les deux compteurs
	 */
	public MyArrayList(int i, int f) {
		ls = 0;
		ps = ct_accTot = i;
		ar = new Object[ps];
		fact = f;
		ct_accCp = 0;
		ct_accLog = 0;
		ct_added = 0;
	}
	
	/**
	 * Retourne la taille logique de l'ArrrayList (le nombre d'éléments stockés)
	 */
	public int size() {
		return ls;
	}
	
	/**
	 * Retourne la taille physique de l'ArrayList (la taille du tableau "en mémoire"
	 */
	public int physicalSize() {
		return ps;
	}
	
	/**
	 * Retourne le ie élément de l'ArrayList. 
	 * Cette méthode lance une exception
	 * si i n'est pas un indice autorisé pour l'ArrayList
	 */
	public Object get(int i) {
		if (i<0 || i>=ls)
			throw new ArrayIndexOutOfBoundsException();
		return ar[i];
	}
	 
	/**
	 * Ajoute l'objet o à la fin de l'ArrayList
	 */
	public void add(Object o) {
		add(ls, o);
	}

	/**
	 * Ajoute l'objet o en position i dans l'ArrayList. Cette méthode 
	 * lance une exception si i n'est pas un indice autorisé pour l'ArrayList
	 */
	public void add(int i, Object o) {
		adjustSize(i);
		ar[i] = o;
		ct_added++;
	}
	
	/**
	 * Retourne la taille physique de l'ArrayList après n ajouts d'éléments
	 */
	public int getV() {
		return ps;
	}
	
	/**
	 * Retourne le nombre de copies cumulées effectuées après n ajouts d'éléments
	 */
	public int getW() {
		return ct_accCp;
	}
	
	/**
	 * Retourne le pourcentage d'utilisation effective du tableau 
	 * après n ajouts d'éléments
	 */
	public double getX() {
		return (double)ls/ps;
	}
	
	/**
	 * Retourne le pourcentage moyen de l'utilisation effective 
	 * du tableau après n ajouts d'éléments.
	 */
	public double getY() {
		return (double)ct_accLog/ct_accTot/ct_added;
	}
	
	/**
	 * Fait grandir le tableau pour stocker un élément de plus,
	 * si nécessaire (elle ne fait peut-être rien)
	 */
	protected void adjustSize(int pos) {
		if (pos<0 || pos>ls)
			throw new ArrayIndexOutOfBoundsException();
		ls++;
		/*
		 * orig 01234*56789
		 * copy 01234 56789
		 */
		if (ls > ps) {
			ps = nextPhysicalSize(ps);
			Object[] nw = new Object[ps];
			System.arraycopy(ar, 0, nw, 0, pos);
			if (pos+1 < ls-1)
				System.arraycopy(ar, pos+1, nw, pos, (ls-1)-pos);
			ct_accCp += ls-1;
			ct_accTot += ps;
			ct_accLog += ls;
			ar = nw; //erase the old array
		}
	}
	
	/**
	 * Détermine la nouvelle taille physique à partir de l'ancienne.
	 */
	 protected abstract int nextPhysicalSize(int cur);
	 
	 /**
	  * Affiche les statistiques demandées dans l'énoncé du TP
	  */
	 public static void printStats(MyArrayList al, int max) {
		for (int i=0; i<max; i++) {
			al.add(42);
			System.out.println(i+" "+al.getV()+" "+al.getW()+" "+al.getX()+" "+al.getY());
		}
		System.out.println(""); //next block
	 }

	/**
	 * Test sur les deux classes
	 */
	public static void main (String args[]) {
		/**
		 * "ça crashe plus... on peut ranger le parapluie."
		 * < Mathieu (ça restera dans l'histoire :p)
		 */
		MyArrayList al;
		
		al = new AdditiveArrayList(2, 1);
		MyArrayList.printStats(al, 10000);
		al = new AdditiveArrayList(2, 10);
		MyArrayList.printStats(al, 10000);
		al = new AdditiveArrayList(2, 100);
		MyArrayList.printStats(al, 10000);
		al = new AdditiveArrayList(100, 10);
		MyArrayList.printStats(al, 10000);
		al = new AdditiveArrayList(100, 100);
		MyArrayList.printStats(al, 10000);
		
		al = new MultiplicativeArrayList(1, 2);
		MyArrayList.printStats(al, 10000);
		al = new MultiplicativeArrayList(1, 3);
		MyArrayList.printStats(al, 10000);
		al = new MultiplicativeArrayList(1, 5);
		MyArrayList.printStats(al, 10000);
		al = new MultiplicativeArrayList(1, 10);
		MyArrayList.printStats(al, 10000);
		al = new MultiplicativeArrayList(100, 5);
		MyArrayList.printStats(al, 10000);
		
	}
}

